package 我的Java学习_算法基础.day_06;

import static java.lang.Math.log;

public class _103_素数的筛法 {
    public static void main(String[] args) {
        long now = System.currentTimeMillis();
        solve1(100000);
        System.out.println("耗时："+(System.currentTimeMillis()-now)+"ms");
        now = System.currentTimeMillis();
        solve2(100000);
        System.out.println("耗时："+(System.currentTimeMillis()-now)+"ms");
    }

    /**
     * 埃氏筛法
     * 需要确定第N个素数的大致大小
     * @param N 第N个素数
     */
    private static void solve1(int N){
        /**
         * N是第N个素数
         * 已知在整数X内大概有X/log(x)个素数
         * 现在逆推：要想求第N个素数，需要的整数范围
         * length就是整数范围
         */
        int n = 2;
        while (n / log(n)<N) {
            n++;
        }
        //开辟一个数组，下标是自然数，值是标记
        //基本思路：筛选法，把非素数标记出来
        int[] arr = new int[n];
        int x = 2;
        while(x<n){
            //标记过了，找下一个
            if(arr[x]!=0){
                x++;
                continue;
            }
            int k =2;
            //对每个x，从2倍开始，对x的k倍，全部标记为-1
            while(x*k<n){
                arr[x*k]=-1;
                k++;
            }
            x++;
        }
        int sum = 0;
        for(int i =2;i<arr.length;i++){
            if(arr[i]==0){
                sum++;
            }
            if(sum==N){
                System.out.println(i);
                return;
            }
        }


    }

    /**
     *耗时长，会超时
     * @param N 第N个素数
     */
    private static void solve2(int N){
        int count = 0;
        int n =2;
        while(count<N){
            if(isPrime(n)){
                count++;
            }
            n++;
        }
        System.out.println(n-1);
    }
    private  static boolean isPrime(int n){
        if(n==1){
            return false;
        }
        for(int i=2;i*i<=n;i++){
            if(n%i==0){
                return false;
            }
        }
        return true;
    }
}
